| 1. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
An Exponential Lower Bound on the Expected Complexity of Sphere Decoding
- 2004
-
In: Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing. ; , s. 393-396
-
Conference paper (peer-reviewed)abstract
- The sphere decoding algorithm is an efficient algorithm used to solve the maximum likelihood detection problem in several digital communication systems. The sphere decoding algorithm has previously been claimed to have polynomial expected complexity. While it is true that the algorithm has an expected complexity comparable to that of other polynomial time algorithms for problems of moderate size it is a misconception that the expected number of operations asymptotically grow as a polynomial function of the problem size. In order to illustrate this point we derive an exponential lower bound on the expected complexity of the sphere decoder.
|
|
| 2. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
Channel dependent termination of the semidefinite relaxation detector
- 2006
-
In: 2006 IEEE International Conference on Acoustics, Speech, and Signal Processing. - NEW YORK, NY : IEEE. ; , s. 185-188
-
Conference paper (peer-reviewed)abstract
- We study the problem of semidefinite relaxation (SDR) for detection of symbols transmitted over a general MIMO channel. In the SDR detector the maximum likelihood detection problem is relaxed into a semidefinite program (SDP) which is solved numerically using an interior-point path-following algorithm. Herein, we provide a criteria which, based on the channel matrix realization, determine the accuracy required by the SDP solver to give a good bit error rate performance of the overall SDR detector. This also reduce the complexity of the SDR detector as it limits the number of interior iterations required in the SDP solver. The performance is demonstrated through simulations.
|
|
| 3. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
Detection Based on Relaxation in MIMO Systems
- 2008. - 1
-
In: Handbook on Advancements in Smart Antenna Technologies for Wireless Networks. - : Premier Reference Source. - 9781599049885 - 1599049880 ; , s. 308-327
-
Book chapter (other academic/artistic)abstract
- This chapter takes a closer look at a class of MIMO detention methods, collectively referred to as relaxation detectors. These detectors provide computationally advantageous alternatives to the optimal maximum likelihood detector. Previous analysis of relaxation detectors have mainly focused on the implementation aspects, while resorting to Monte Carlo simulations when it comes to investigating their performance in terms of error probability. The objective of this chapter is to illustrate how the performance of any detector in this class can be readily quantified thought its diversity gain when applied to an i.i.d. Rayleigh fading channel, and to show that the diversity gain is often surprisingly simple to derive based on the geometrical properties of the detector.
|
|
| 4. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
Full diversity detection in MIMO systems with a fixed-complexity sphere decoder
- 2007
-
In: 2007 IEEE International Conference on Acoustics, Speech, and Signal Processing. - : IEEE. ; , s. 49-52
-
Conference paper (peer-reviewed)abstract
- The fixed-complexity sphere decoder (FSD) has been previously proposed for multiple input-multiple output (MIMO) detection to overcome the two main drawbacks of the original sphere decoder (SD), namely its variable complexity and sequential structure. As such, the FSD is highly suitable for hardware implementation and has shown remarkable performance through simulations. Herein, we explore the theoretical aspects of the algorithm and prove that the FSD achieves the same diversity order as the maximum likelihood detector (MLD). Further, we show that the coding loss can be made negligible in the high signal to noise ratio (SNR) regime with a significantly lower complexity than that of the MLD.
|
|
| 5. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
High diversity detection using semidefinite relaxation
- 2006
-
In: 2006 Fortieth Asilomar Conference on Signals, Systems and Computers. - 9781424407842 ; , s. 2082-2086
-
Conference paper (peer-reviewed)abstract
- Receiver diversity is an important measure of a receivers robustness towards fading in wireless communications. For the detection of binary symbols transmitted over a general MIMO channel, the semidefinite relaxation (SDR) detector is a computationally attractive alternative to exact ML detection. In the SDR detector, the hard combinatorial optimization problem arising in the ML detector is relaxed into a simple convex optimization problem followed by component wise threshold decisions. In this work, we argue that the SDR detector win provide an increase in diversity over simpler decoder structures such as the ZF and NMSE detectors. Specifically, for the case of uncoded V-BLAST transmission over a MIMO channel with real valued i.i.d. Gaussian channel coefficients we present an analytic result stating that the SDR detector achieves the maximum possible receiver diversity.
|
|
| 6. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
On the complexity of sphere decoding in digital communications
- 2005
-
In: IEEE Transactions on Signal Processing. - : IEEE Signal Processing Society. - 1053-587X .- 1941-0476. ; 53:4, s. 1474-1484
-
Journal article (peer-reviewed)abstract
- Sphere decoding has been suggested by a number of authors as an efficient algorithm to solve various detection problems in digital communications. In some cases, the algorithm is referred to as an algorithm of polynomial complexity without clearly specifying what assumptions are made about the problem structure. Another claim is that although worst-case complexity is exponential, the expected complexity of the algorithm is polynomial. Herein, we study the expected complexity where the problem size is defined to be the number of symbols jointly detected, and our main result is that the expected complexity is exponential for fixed signal-to-noise ratio (SNR), contrary to previous claims. The sphere radius, which is a parameter of the algorithm, must be chosen to ensure a nonvanishing probability of solving the detection problem. This causes the exponential complexity since the squared radius must grow linearly with problem size. The rate of linear increase is, however, dependent on the noise variance, and thus, the rate of the exponential function is strongly dependent on the SNR. Therefore sphere decoding can be efficient for some SNR and problems of moderate size, even though the number of operations required by the algorithm strictly speaking always grows as an exponential function of the problem size.
|
|
| 7. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
On the limits of sphere decoding
- 2005
-
In: 2005 IEEE International Symposium on Information Theory (ISIT), Vols 1 and 2. - NEW YORK : IEEE. - 0780391500 ; , s. 1691-1695
-
Conference paper (peer-reviewed)abstract
- The sphere decoder has emerged as one of the most promising techniques for maximum likelihood detection of symbols transmitted over a general MIMO channel. Although efficient for problems of moderate size it is known that the original sphere decoder is of exponential (expected) complexity which limits its usage for large scale problems. However, at this stage, many alterations and improvements over the original algorithm have appeared in the literature. Herein we study a generic sphere decoder for the i.i.d. Rayleigh fading MIMO channel. The detection ordering and search radius (parameters of the algorithm) are allowed to be arbitrary functions of the decoder input, the only restriction being that the search radius is chosen such that the detection problem is solved. It is shown that the set of problem instances solvable by the sphere decoder in less than exponential time will tend to zero with increasing problem size. This extends previous results by providing a statement which is stronger than exponential expected complexity while relaxing the assumptions regarding the specific decoder implementation.
|
|
| 8. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
On the maximal diversity order of spatial multiplexing with transmit antenna selection
- 2007
-
In: IEEE Transactions on Information Theory. - : IEEE. - 0018-9448 .- 1557-9654. ; 53:11, s. 4273-4276
-
Journal article (peer-reviewed)abstract
- Zhang et al. recently derived upper and lower bounds on the achievable diversity of an N-R X N-T, i.i.d. Rayleigh fading multiple antenna system using transmit antenna selection, spatial multiplexing and a linear receiver structure. For the case of L = 2 transmitting (out of N-T available) antennas the bounds are tight and therefore specify the maximal diversity order. For the general case with L
|
|
| 9. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
Parallel implementation of a soft output sphere decoder
- 2005
-
In: 2005 39th Asilomar Conference on Signals, Systems and Computers. - NEW YORK : IEEE. ; , s. 581-585
-
Conference paper (peer-reviewed)abstract
- Transmission at rates close to capacity over fading multiple antenna channels can be achieved by concatenating inner space-time block codes and powerful outer codes such as turbo or LDPC codes. However, in such systems, computation of the required soft information, or log-likelihood ratios (LLR), for the bits transmitted over the channel is rather complex and some form of approximations are typically used. Herein, we show how the complexity of computing the max-log approximation of the LLR can be reduced by computing all LLR values simultaneously using a parallel sphere decoder implementation.
|
|
| 10. |
- Jaldén, Joakim, 1976-, et al.
(author)
-
Reducing the average complexity of ML detection using semidefinite relaxation
- 2005
-
In: 2005 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING. - 0780388747 ; , s. 1021-1024
-
Conference paper (peer-reviewed)abstract
- Maximum likelihood (ML) detection of symbols transmitted over a MIMO channel is generally a difficult problem due to its NP-hard nature. However, not every instance of the detection problem is equally hard. Thus, the average complexity of an ML detector may be significantly smaller than its worst-case counterpart. This is typically true in the high SNR regime where the received signals are closer to the noise free transmitted signals. Herein, a method which may be used to lower the average complexity of any ML detector is proposed. The method is based on the ability to verify if a symbol estimate is ML, using an optimality condition provided by the near-ML semidefinite relaxation technique. The average complexity reduction advantage of the proposed method is confirmed by numerical results.
|
|
